//给定一个二叉树，判断它是否是高度平衡的二叉树
//时间复杂度为O(N^2)版：依次判断每个结点的左右高度差是否满足条件
class Solution1 {
    public boolean isBalanced(TreeNode root) {
        //空树(也是递归的结束条件)
        if(root == null) return true;
        //左右子树的高度差
        if(Math.abs(GetHeight(root.left)-GetHeight(root.right))>1)
            return false;
        //继续递归求左右结点是否平衡(因为要求每个节点的左右两个子树的高度差的绝对值不超过 1)
        return isBalanced(root.left)&&isBalanced(root.right);

    }
    //获取子树的高度
    public int GetHeight(TreeNode root) {
        if(root==null) return 0;
        return 1+Math.max(GetHeight(root.left),GetHeight(root.right));
    }
}
//字节面试题改进版
class Solution2 {
    public boolean isBalanced(TreeNode root) {
        //空树(也是递归的结束条件)
        if(root == null) return true;
        return GetHeight(root)>=0;
    }
    //获取子树的高度
    public int GetHeight(TreeNode root) {
        if(root==null) return 0;
        int HeightLeft = GetHeight(root.left);
        //如果左树高度=-1,直接不用计算右树高度，返回-1即可
        if(HeightLeft<0) {
            return -1;
        }
        int HeightRight = GetHeight(root.right);
        //(0)-(-1)也是<=1，所以得加上条件HeightLeft>=0&&HeightRight>=0
        if(HeightLeft>=0&&HeightRight>=0&&Math.abs(HeightLeft-HeightRight)<=1) {
            return 1+Math.max(HeightLeft,HeightRight);
        } else {
            //不平衡直接返回-1
            return -1;
        }

    }
}